/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: 23735
 * Date: 2023-01-17
 * Time: 22:44
 */
public class Solution {
//     思路:
//     滑动窗口
//     j 是往下遍历的新的右边界
//     向前找 找满足条件的最小的 i, 使得>i 时, 连乘的结果>k, <=i, 连乘的结果>=k
//     窗口往下滑动时, 即right=j+1, 那么左边界最小是 i, 因为<i, 连乘的结果早就>k了
//     [i,j]是某个满足条件的窗口, count+= j-i+1
//     为什么是 j-i+1, 可以想象一下, 整个数组的乘积都<k 的情况
//     窗口每往后扩大一个单位, 就计算了一次
    public int numSubarrayProductLessThanK(int[] nums, int k) {
        int count=0; // 结果
        int product=1; // 乘积
        int len=nums.length;
        int left=0;
        int right=0;
        while(right<len){
            product*=nums[right];
            // 通过缩短左边界, 寻找 满足条件的最小的左边界
            while(left<=right&&product>=k){
                product/=nums[left];
                left++;
            }
            // 更新结果
            count+=right-left+1;
            // 窗口扩大右边界
            right++;
        }
        return count;
    }
}
